package com.ddd.demo.test;

import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {

        int[] arr = new int[]{2, 3, 1, 4, 5};
        int[] ints = m1Sort(arr);

        System.out.println("Arrays.toString(ints) = " + Arrays.toString(ints));
    }

    private static int[] m1Sort(int[] arr) {
        int length = arr.length;

        if(length < 2){
            return arr;
        }

        int mid = length / 2;

        int[] left = Arrays.copyOfRange(arr, 0 ,mid);
        int[] right = Arrays.copyOfRange(arr, mid, length);

        return merge(m1Sort(left),m1Sort(right));

    }

    private static int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];

        for (int index = 0,i=0,j=0; index < (left.length + right.length); index++) {

            if(i >= left.length){
                result[index] = right[j++];
            }else if(j >= right.length){
                result[index] = left[i++];
            }else if(left[i] > right[j]){
                result[index] = right[j++];
            }else{
                result[index] = left[i++];
            }
        }

        return result;
    }

    @Test
    public void t1() {
        int[] arr = new int[]{2, 3, 1, 4, 5};
        test(arr);
    }

    private static void test(int[] arr) {
        int length = arr.length;

        int mid = length / 2;

        int[] left = Arrays.copyOfRange(arr, 0 ,mid);
        int[] right = Arrays.copyOfRange(arr, mid, length);

        System.out.println("left = " + Arrays.toString(left));
        System.out.println("right = " + Arrays.toString(right));

    }

}
